package com.lry.basic.algorithm.dp;

public class Fib {
    public static void main(String[] args) {
        System.out.println(fib(10));

        System.out.println(fib2(100));

        System.out.println(fib3(100,1,1));

        System.out.println(fib4(100));

        System.out.println(fib5(100));

        System.out.println(fib6(100));
    }

    //1 1 2 3 5 8 13
    public static long fib(int n){
        if(n==1||n==2){
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }


    static long[] memory = new long[10000];
    public static long fib2(int n){
        if(n==1||n==2){
            return 1;
        }
        if(memory[n]>0){
            return memory[n];
        }
        return memory[n] = fib2(n-1)+fib2(n-2);
    }


    public static long fib3(int n,long a,long b){
        if(n<=1){
            return a;
        }
        return fib3(n-1,b,a+b);
    }

    static long[] dp = new long[10000];
    public static long fib4(int n){
        dp[1] = 1;
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    public static long fib5(int n) {
        long a = 1;
        long b = 1;
        long ab = 1;
        for(int i=3;i<=n;i++){
            ab = a+b;
            a = b;
            b = ab;
        }
        return ab;
    }


    //对不上
     public static long  fib6(int n) {
        double c = Math.sqrt(5);
        return (long) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
    }

}


